/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/remove-duplicates-from-sorted-list-ii
   @Language: C++
   @Datetime: 16-02-09 08:24
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */


class Solution{
public:
	/**
	 * @param head: The first node of linked list.
	 * @return: head node
	 * Tip : p record last node, head is current node, q is next node
	 *       traversal list and judge current node if equal to q
	 */
	ListNode * deleteDuplicates(ListNode *head) {
		// write your code here
		ListNode H(-1), *p, *q;
		for(H.next=head, p=&H; head && (q=head->next);){
			if(head->val != q->val){
				p = head;
				head = q;
				continue;
			}
			for(; q && head->val==q->val; q=q->next){
				delete head;	// recommend delete, if not can also ac
				p->next = head = q;
			}
			delete head;		// recommend delete, if not can also ac
			p->next = head = q;
		}
		return H.next;
	}
};
